#include "status.h"
#include <stdio.h>
#include <stdlib.h>

typedef struct node{
	datatype data;
	int lthread;
	struct node *lchild;
	struct node *rchild;
	int rthread;
}bitree;


typedef struct{
	bitree *root;
	bitree *cur;
	int nextcomplete;
}threadbitree;

void inthread(bitree *cur,bitree **pre){
	if(cur==NULL)return;
	inthread(cur->lchild,pre);
	if(cur->lchild==NULL){
		cur->lthread=1;
		cur->lchild=*pre;
	}else{
		cur->lthread=0;
	}
	if(cur->rchild!=NULL) cur->rthread=0;
	else cur->rthread=1;
	if((*pre)->rchild==NULL){
		(*pre)->rthread=1;
		(*pre)->rchild=cur;
	}else{
		cur->rthread=0;
	}
	*pre=cur;
	inthread(cur->rchild,pre);
}
void createinthread(bitree **root){
	bitree *t =*root;
	bitree *cur,*pre=*root;
	*root=(bitree*)malloc(sizeof(bitree));
	if(t==NULL){
		(*root)->lthread=0;
		(*root)->rthread=1;
		(*root)->lchild=*root;
		(*root)->rchild=*root;
	}else{
		cur=t;
		(*root)->lchild=t;
		(*root)->lthread=0;
		inthread(cur,&pre);
		pre->rchild=*root;
		pre->rthread=1;
		(*root)->rchild=pre;
		(*root)->rthread=1;
	}
}
void threadinit(threadbitree *tree,bitree *root){
	tree->root=root;
	tree->cur=root;
	if(root==NULL) tree->nextcomplete=0;
	else tree->nextcomplete=1;
}
void first(threadbitree *tree){
	tree->cur=tree->root;
	while(tree->cur->lthread==0)
		tree->cur=tree->cur->lchild;
	if(tree->cur==tree->root) tree->nextcomplete=1;
	else tree->nextcomplete=0;
}
void next(threadbitree *tree){
	bitree *p=tree->cur->rchild;
	if(tree->nextcomplete==1) return;
	if(tree->cur->rthread==0)
		while(p->lthread) p=p->lchild;
	tree->cur=p;
	if(tree->cur==tree->root) tree->nextcomplete=1;
}
int endofnext(threadbitree *tree){
	return tree->nextcomplete;
}
bitree *gettreenode(datatype item,bitree *left,bitree *right){
	bitree *p;
	p=(bitree *)malloc(sizeof(bitree));
	p->data=item;
	p->lchild=left;
	p->rchild=right;
	return p;
}
void makechartree(threadbitree **root){
	threadbitree *b,*c,*d,*e,*f,*g;
	g=gettreenode('G',NULL,NULL);
	d=gettreenode('D',NULL,g);
	b=gettreenode('B',d,NULL);
	e=gettreenode('E',NULL,NULL);
	f=gettreenode('F',NULL,NULL);
	c=gettreenode('C',e,f);
	*root=gettreenode('A',b,c);
}
void printdata(bitree *p){
	if(p==NULL)return;
	printf("%d %c %d\n",p->lthread,p->data,p->rthread);
}
void inorder(bitree *root,void visit(bitree *m)){
	if(root==NULL) return;
	inorder(root->lchild,visit);
	visit(root);
	inorder(root->rchild,visit);
}
int main(){
	bitree *root;
	threadbitree tree;
	makechartree(&root);
	inorder(root,printdata);
	printf("********************************\n");
	createinthread(&root);
//	threadinit(&tree,root);
//	for(first(&tree);!endofnext(&tree);next(&tree))
//		printf("%c  ",tree.cur->data);
	inorder(root,printdata);
}
